package q473_makesquare;

import java.util.Arrays;

/*
此题完全是698题的子题
直接参考698题
 */
public class Solution {
    public boolean makesquare(int[] matchsticks) {
        if (matchsticks.length < 4) return false;
        int sum = 0;
        for (int stick : matchsticks) sum += stick;
        if (sum % 4 != 0) return false;

        Arrays.sort(matchsticks);
        int[] bucket = new int[4];
        return dfs(matchsticks, matchsticks.length - 1, bucket, sum / 4);
    }

    private boolean dfs(int[] matchsticks, int index, int[] bucket, int target) {
        if (index == -1) return true;

        for (int i = 0; i < 4; i++) {
            if (matchsticks[index] + bucket[i] > target) continue;

            bucket[i] += matchsticks[index];

            if (dfs(matchsticks, index - 1, bucket, target)) return true;

            bucket[i] -= matchsticks[index];

            if (bucket[i] == 0) break;
        }

        return false;
    }
}
